/* exercice 2 */

q1(_):-fail.
q2(P):-not(P).
q3(_).

/*exercice 3*/

somme([],0).
somme([X|L],R):-somme(L,T), R is X+T.

aplatir([],[]).
aplatir([X|L],R):-aplatir(L,T), append(X,T,R).

pair([],0).
pair([N|L],R):-pair(L,T), (N mod 2 =:= 0 -> R is T+1; R is T).


fold_right(_,E,[],E).
fold_right(F,E,[X|L],R):-fold_right(F,E,L,S),Q=..[F,X,S,R],Q.


put_behind(X,[],[X]).
put_behind(X,[Y|L],[Y|T]):-put_behind(X,L,T).

/* iterer put_behind a droite pour inverser n'est pas efficace, complexite quadratique */

fold_left(_,E,[],E).
fold_left(F,E,[X|L],R):-Q=..[F,E,X,Z],Q,fold_left(F,Z,L,R).

put_ahead(L,X,[X|L]).
reverse(L,R):-fold_left(put_ahead,[],L,R)

/* complexité lineaire */

/*exercice 4*/

move((N,P),(M,Q)):-  N>0, min(N,P,K), inbetween(1,K,R), M is N-R, Q is 2*R.

inbetween(X,Y,X):-X=<Y.
inbetween(Y,X,Z):-Y<X, S is Y+1, inbetween(S,X,Z).


:-dynamic(gagne)
gagne(P):-move(P,Q), not(gagne(Q)),asserta(gagne(P)).